# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
#
# class Solution:
#     def mergeTwoLists(self, l1, l2):
#         """
#         :type l1: ListNode
#         :type l2: ListNode
#         :rtype: ListNode
#         """
#         # if l1 is None and l2 is None:
#         #     return None
#         # new_list = ListNode(0)
#         # pre = new_list
#         # while l1 is not None and l2 is not None:
#         #     if l1.val < l2.val:
#         #         pre.next = l1
#         #         l1 = l1.next
#         #     else:
#         #         pre.next = l2
#         #         l2 = l2.next
#         #     pre = pre.next
#         # if l1 is not None:
#         #     pre.next = l1
#         # else:
#         #     pre.next = l2
#         # return new_list.next
#
#         if l1 is None:
#             return l2
#         elif l2 is None:
#             return l1
#         elif l1.val < l2.val:
#             l1.next = self.mergeTwoLists(l1.next, l2)
#             return l1
#         else:
#             l2.next = self.mergeTwoLists(l1, l2.next)
#             return l2
#
#     def isPalindrome(self, head: ListNode) -> bool:
#             # 预处理
#         if head is None or head.next is None:
#             return True
#         recnct, slow, fast = head, head, head
#         newhead = None
#         # 遍历链表
#         while fast and fast.next:
#             fast = fast.next.next
#             tmp = slow
#             slow = slow.next
#             # 反转链表（前半部分）
#             tmp.next = newhead
#             newhead = tmp
#         # 连接中间断裂的链表
#         recnct.next = slow
#         ps = newhead
#         # 判断链长为奇为偶？
#         pf = slow.next if fast else slow
#         # 遍历前半部分、后半部分链表，判断对应值是否相等？
#         while pf:
#             if ps.val != pf.val:
#                 return False
#             ps = ps.next
#             pf = pf.next
#         return True
#
#
# l1 = ListNode(1)
# n1 = ListNode(2)
# n2 = ListNode(4)
#
# l1.next = n1
# n1.next = n2
#
#
# l2 = ListNode(1)
# m1 = ListNode(3)
# m2 = ListNode(5)
#
# l2.next = m1
# m1.next = m2
# l = Solution()
# l.isPalindrome(l1)

# nums1 = [1,2,3,4,0,0,0]
# nums2 = [5,6,7,8]
# nums1 = nums1[:5] + nums2[:3]
# print(nums1)

# x =1
# # y =4
# # r = bin(3)
# # r <<= 1
# # n = 0b00000010100101000001111010011100
# # m = 0b00111001011110000010100101000000
# # b = bin(y)
# # a = int(n)
# # print(b)
# # print(a)
# # print(m)
# # print(str(n))
# # print(r)
# a = [2,3,4,5,6,7,8,10]
# # b = sum(a)
# # print(b)

# class Solution:
# #     def isValid(s: str) -> bool:
# #         dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
# #         stack = ['?']
# #         for c in s:
# #             if c in dic: stack.append(c)
# #             elif dic[stack.pop()] != c: return False
# #         return len(stack) == 1
# #
# # s = Solution
# # a = s.isValid("()[]{}")

# print(round(2.355,2))
# n = 10
# ans = []
# for i in range(n):
#     ans.append(i)
# print(ans)

# n = 10
# ans = []
# a = True
# for i in range(2, n + 1):
#     for j in range(2, i):
#         if i % j == 0:
#             a = False
#             break
#     if a:
#         ans.append(i)
#     a = True
# print(ans)

# n = 10
# prime = [1] * n
# prime[0] = prime[1] = 0
# for i in range(2, int(n**0.5) + 1):
#     if prime[i] == 1:
#         prime[i * i:n:i] = [0] * len(prime[i * i:n:i])
# print(sum(prime))
import random

dic = {"I": 1,
       "V": 5,
       "X": 10,
       "L": 50,
       "C": 100,
       "D": 500,
       "M": 1000}
a = []
n = "MMCMXCIV"
sum = 0
l = len(n)
for i in range(l-1):
    if n[i] == "I" and(n[i+1]=="V" or n[i+1] == "X"):
        sum += -dic["I"]
    elif n[i] == "X" and (n[i+1] == "L" or n[i+1] == "C"):
        sum += -dic["X"]
    elif n[i] == "C" and(n[i+1]=="D" or n[i+1] == "M"):
        sum += -dic["C"]
    else:
        sum += dic[n[i]]
sum +=dic[n[-1]]
print(sum)

num = 2994
i = num // 1000
ans = "M" * i
num = num % 1000
i = num // 100
if i <4:
    ans += "C"*i
elif 3<i<5:
    ans +=("CD")
elif 4<i<9:
    ans +=("D"+(i-5)*"C")
else:
    ans += ("CM")
num = num % 100
i = num // 10
if i <4:
    ans += "X"*i
elif 3<i<5:
    ans +=("XL")
elif 4<i<9:
    ans +=("L"+(i-5)*"X")
else:
    ans += ("XC")
i = num % 10
if i <4:
    ans += "I"*i
elif 3<i<5:
    ans +=("IV")
elif 4<i<9:
    ans +=("V"+(i-5)*"I")
else:
    ans += ("IX")
print(ans)


class Solution:
    def __init__(self, nums):
        self.array = nums
        self.original = list(nums)

    def reset(self):
        self.array = self.original
        self.original = list(self.original)
        return self.array

    def shuffle(self):
        aux = list(self.array)

        for idx in range(len(self.array)):
            remove_idx = random.randrange(len(aux))
            self.array[idx] = aux.pop(remove_idx)

        return self.array

    def __init__(self):
        # 数据栈
        self.data = []
        # 辅助栈
        self.helper = []

    def push(self, x):
        self.data.append(x)
        if len(self.helper) == 0 or x <= self.helper[-1]:
            self.helper.append(x)
        else:
            self.helper.append(self.helper[-1])

    def pop(self):
        if self.data:
            self.helper.pop()
            return self.data.pop()

    def top(self):
        if self.data:
            return self.data[-1]

    def getMin(self):
        if self.helper:
            return self.helper[-1]

